package data_structure.mooc;

import data_structure.helper.ArrayGenerator;
import data_structure.helper.SortingHelper;

public class BinarySearch {

    private BinarySearch() {

    }

    public static <E extends Comparable<E>> int searchR(E []arr,E target){

        if(!SortingHelper.isSorted (arr)){
            throw new RuntimeException ("数组没有从小到大排序");
        }

        return searchR (arr,target,0,arr.length-1);
    }

    private static <E extends Comparable<E> > int searchR(E []arr,E target,int left,int right) {

        if(left>right)return -1;
        int mid=left+(right-left)/2;
        if(target.compareTo (arr[mid])==0){
            return mid;
        }else if(target.compareTo (arr[mid])>0){
            return searchR (arr,target,mid+1,right);
        }else{
            return searchR (arr,target,left,mid-1);
        }
    }

    public static <E extends Comparable<E>> int search(E []arr,E target){

        if(!SortingHelper.isSorted (arr)){
            throw new RuntimeException ("数组没有从小到大排序");
        }
        int left=0;
        int right=arr.length -1;
        int mid;

        while(left<=right){
            mid=left+(right-left)/2;
            if(target.compareTo (arr[mid])==0){
                return mid;
            }
            if(arr[mid].compareTo(target) > 0){
                right=mid-1;
            }
            if (arr[mid].compareTo(target) < 0) {
                left=mid+1;
            }
        }
        return -1;
    }

    /**
     * 寻找大于target的最小的一个值
     * @param arr
     * @param target
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E> > int upper(E []arr,E target){
        if(!SortingHelper.isSorted (arr)){
            throw new RuntimeException ("数组没有从小到大排序");
        }
        int left=0;
        //arr[data.length]可能是返回的结果，只不过是为空
        int right=arr.length;
        while(left<right){
            int mid=left+(right-left)/2;
            if(arr[mid].compareTo(target) <= 0){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return left;
    }

    /**
     * 给定目标值，在数组中查找，如果找到了目标值，返回目标值的最大下标，找不到的话，返回大于目标值的最小下标
     * @param arr
     * @param target
     * @param <E>
     * @return
     */

    public static <E extends Comparable<E> > int upperFloor(E []arr,E target){
        int u=upper (arr,target);
        if(u-1>=0&&arr[u-1].compareTo (target)==0){
            return u-1;
        }else{
            return u;
        }
    }

    /**
     * 找到>= target 的最小值索引
     * @param data
     * @param target
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int upperCeil(E[] data, E target){

        if(!SortingHelper.isSorted (data)){
            throw new RuntimeException ("数组没有从小到大排序");
        }

        int l = 0, r = data.length;
        // 在 data[l, r] 中寻找解
        while(l < r){
            int mid = l + (r - l) / 2;
            // 在 upper 中，这里是 data[mid].compareTo(target) <= 0
            // 但是，对于 lower_ceil 来说，在 data[mid] == target 的时候，有可能是解
            // 所以在等于的情况下，不能排除掉 data[mid] 的值。在等于的情况下，应该归入下面的 else 中做处理
            // 也就是，data[mid] == target 的时候可能是解，也可能有更小的解在左边，应该去更新右边界
            if(data[mid].compareTo(target) < 0)
                l = mid + 1;
            else
                r = mid;
        }
        return l;
    }

    /**
     * 找到小于target值的最大的索引
     * @param arr
     * @param target
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E> > int lower(E[] arr, E target) {
        int l=-1;
        int r=arr.length-1;
        while(l<r){
            //边界向上取整
            int mid=l+(r-l+1)/2;
            if(arr[mid].compareTo(target) < 0){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        return l;
    }

    /**
     * 找到<=target值的最大索引
     * @param arr
     * @param target
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E> > int lowerCeil(E[] arr, E target){

        int l=-1;
        int r=arr.length - 1;

        while(l<r){
            int mid=l+(r-l+1)/2;
            //此时判断的条件为<=0
            if(arr[mid].compareTo(target) <= 0){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        return l;
    }

    /**
     * 给定目标值，在数组中查找，如果找到了目标值，返回目标值的最小下标，找不到的话，返回小于目标值的最大下标
     * @param arr
     * @param target
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E> > int lowerFloor(E[] arr, E target){

        int lower=lower (arr,target);
        if(lower+1<arr.length&&arr[lower+1].compareTo(target) == 0){
            return lower+1;
        }else{
            return lower;
        }
    }


    public static void main(String[] args) {
        Integer []arr= ArrayGenerator.generateOrderedArray (10);
        int r0=upper(arr,5);
        int r1=lower (arr,18);
        int r2=lower (arr,29);
        int r3=lower (arr,100000000);
        int i=0;
    }
}
